package day18;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：[[5,4,11,2],[5,8,4,5]]
 * 示例 2：
 *
 *
 * 输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 *
 */
public class Solution3 {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(new ArrayList<>(),root,targetSum,0);
        return list;
    }
    public void dfs(List<Integer> list1,TreeNode root,int targetSum,int sum){
        if(root==null){
            return;
        }
        if(root.right==null&&root.left==null&&sum+ root.val==targetSum){
            list1.add(root.val);
            List<Integer> index = new ArrayList<>();
            for (Integer integer : list1) {
                index.add(integer);
            }
            list.add(index);
            list1.remove(list1.size()-1);
            return;
        }
        sum+=root.val;
        list1.add(root.val);
        dfs(list1,root.right,targetSum,sum);
        dfs(list1,root.left,targetSum,sum);
        list1.remove(list1.size()-1);
    }
}
